[백준]단계별_기본수학2

n = int(input())
is_prime = list(map(int, input().split()))


ans = 0
for i in is_prime:
    count = 0
    for j in range(1, i+1):
        if i % j == 0:
            count += 1
    if count == 2:
        ans += 1

print(ans)

start = int(input())
end = int(input())

start_end = range(start, end+1)
is_prime = []

for i in range(len(start_end)):
    count = 0
    for j in range(1, start_end[i] + 1):
        if start_end[i] % j == 0:
            count += 1
    if count == 2:
        is_prime.append(start_end[i])

if not is_prime:
    print(-1)

else:
    print(sum(is_prime))
    print(min(is_prime))

num = int(input())

# 분해가 전부 될때까지 loop 돌립니다.
while num != 1:
    for i in range(2, num + 1):
        # 나눠지면 출력하고,
        # 다음을 위해 해당 수로 num을 나눠줍니다.
        if(num % i == 0):
            print(i)
            num = num // i
            break

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True


M, N = map(int, input().split())

for i in range(M, N + 1):
    if isPrime(i):
        print(i)

while True:
    n = int(input())
    if n == 0:
        break

    large = n * 2
    # 마지막 index 검출을 위해 +1
    is_prime = [1] * (large + 1)

    for i in range(2, int(large**0.5)+1):
        for j in range(i+i, large+1, i):
            is_prime[j] = 0

    is_prime = is_prime[n+1:large+1]
    print(is_prime.count(1))

import math


def findPrime(n):
    # n 개수만큼 1로 초기화
    is_primes = [True] * (n+1)
    # 제곱근을 이용하여 연산횟수를 줄임
    max_length = int(math.sqrt(n))+1

    # 0, 1 인덱스는 소수가 아니라 2부터 인덱스 시작
    for i in range(2, max_length):
        # 에라토스테네스 체 이용해 소수가 아닌 것들을 판별 / 전체배열 탐색
        for j in range(i+i, n+1, i):
            is_primes[j] = False

    # 소수인 것들만 배열에 저장
    return [x for x in range(2, n) if is_primes[x] == True]


T = int(input())

for _ in range(T):
    n = int(input())
    # 2중 for문을 탈출하기 위한 변수
    loop = True

    primes = findPrime(n)
    # 소수 값들만 가지고 있는 배열에서 n/2를 해 가장 큰 값을 찾음
    # 왜냐하면 두 개의 소수를 더해야하니까 "/2" 를 해서 가장 큰 값을 찾고 밑에서 for문을 가장 높은 순에서 내림차순으로 돌림
    idx = max([i for i in range(len(primes)) if primes[i] <= n/2])

    # 위에서 나온 가장 큰 index에서부터 내림
    for i in range(idx, -1, -1):
        for j in range(i, len(primes)):
            if primes[i] + primes[j] == n:
                print(f'{primes[i]} {primes[j]}')
                loop = False
                break
        if loop == False:
            break